home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / network / lrutils.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  7KB  |  245 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)lrutils.c    5.2 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <stdlib.h>
  42. #include <string.h>
  43. #include "lrucache.h"
  44.  
  45. /*
  46.  *  LRUGETPG -- Get a free page from the LRU cache.
  47.  *
  48.  *    This routine grows the cache if necessary, finds an unused page if
  49.  *    it can, and handles flushing dirty buffers to disk.
  50.  *
  51.  *    One of the parameters to this routine (f) is the routine that called
  52.  *    us.  If we have to grow the cache, we call this routine recursively
  53.  *    in order to fill the buffer.  The reason for this is that we have
  54.  *    two interfaces that call lrugetpg().  Lruget() fills a page from disk,
  55.  *    and lrugetnew() just allocates a new (empty) page.
  56.  *
  57.  *    Parameters:
  58.  *        l -- LRU cache to use.
  59.  *        pgno -- page number for which we want a buffer
  60.  *        nread -- pointer to an int to get number of bytes read
  61.  *        f -- who called us
  62.  *
  63.  *    Returns:
  64.  *        (char *) pointer to buffer to use, or NULL on failure.
  65.  *
  66.  *    Warnings:
  67.  *        The buffer returned is locked down until the user does an
  68.  *        explicit lrurelease() on it.
  69.  */
  70.  
  71. char *
  72. lrugetpg(l, pgno, nread, f)
  73.     LRUCACHE *l;
  74.     int pgno;
  75.     int *nread;
  76.     char *(*f)();
  77. {
  78.     CACHE_ENT *ce;
  79.     LRU_ENT *lruent;
  80.     char *buffer;
  81.  
  82.     /* if we're allowed to grow the cache, do so */
  83.     if (l->lru_cursz < l->lru_csize) {
  84.  
  85.         /* get a buffer */
  86.         if ((buffer = (char *) malloc((unsigned) l->lru_psize))
  87.             == (char *) NULL)
  88.             return ((char *) NULL);
  89.  
  90.         /* get and LRU list entry */
  91.         if ((lruent = (LRU_ENT *) malloc((unsigned) sizeof(LRU_ENT)))
  92.             == (LRU_ENT *) NULL)
  93.             return ((char *) NULL);
  94.         lruent->l_buffer = buffer;
  95.         lruent->l_pgno = pgno;
  96.         lruent->l_flags = NULL;
  97.  
  98.         /* manage spaghetti */
  99.         lruent->l_prev = (LRU_ENT *) NULL;
  100.         lruent->l_next = l->lru_head;
  101.         if (l->lru_head != (LRU_ENT *) NULL)
  102.             l->lru_head->l_prev = lruent;
  103.         l->lru_head = lruent;
  104.         if (l->lru_tail == (LRU_ENT *) NULL)
  105.             l->lru_tail = lruent;
  106.  
  107.         /* add it to the hash table */
  108.         ce = lruhashput(l, pgno, lruent);
  109.         l->lru_cursz++;
  110.     } else {
  111.         lruent = l->lru_tail;
  112.  
  113.         /* find the oldest unused buffer */
  114.         while (lruent != (LRU_ENT *) NULL
  115.                && !(lruent->l_flags & F_FREE))
  116.             lruent = lruent->l_prev;
  117.  
  118.         /* if no free buffer was found, we have to grow the cache */
  119.         if (lruent == (LRU_ENT *) NULL) {
  120.             if (lrugrow(l) < 0)
  121.                 return ((char *) NULL);
  122.             return ((*f)((LRU) l, pgno, nread));
  123.         }
  124.  
  125.         /* okay, found a free buffer -- update hash table and list */
  126.         ce = lruhashget(l, lruent->l_pgno);
  127.         if (lruhashdel(l, lruent->l_pgno) < 0)
  128.             return ((char *) NULL);
  129.  
  130.         /* flush the old page to disk, if necessary */
  131.         if (lruent->l_flags & F_DIRTY)
  132.             if (lruflush(l, lruent) < 0)
  133.                 return ((char *) NULL);
  134.  
  135.         /* update stats, hash table, and list */
  136.         lruent->l_pgno = pgno;
  137.         lruhead(l, lruent);
  138.         ce = lruhashput(l, pgno, lruent);
  139.         buffer = lruent->l_buffer;
  140.     }
  141. #ifdef lint
  142.     ce = ce;
  143. #endif /* lint */
  144.  
  145.     /* lock this page down */
  146.     lruent->l_flags &= ~F_FREE;
  147.  
  148.     return (buffer);
  149. }
  150.  
  151. /*
  152.  *  LRUHEAD -- Move an LRU list entry to the head of the list.
  153.  *
  154.  *    The head of the list is where the most recently used item goes.
  155.  *
  156.  *    Parameters:
  157.  *        l -- LRU cache
  158.  *        lruent -- entry to move to the head of the list
  159.  *
  160.  *    Returns:
  161.  *        None
  162.  *
  163.  *    Side Effects:
  164.  *        Updates the cache's head and tail pointers as required.
  165.  */
  166.  
  167. void
  168. lruhead(l, lruent)
  169.     LRUCACHE *l;
  170.     LRU_ENT *lruent;
  171. {
  172.     LRU_ENT *next;
  173.     LRU_ENT *prev;
  174.  
  175.     if (l->lru_head == lruent)
  176.         return;
  177.  
  178.     next = lruent->l_next;
  179.     prev = lruent->l_prev;
  180.     lruent->l_prev = (LRU_ENT *) NULL;
  181.     lruent->l_next = l->lru_head;
  182.     l->lru_head->l_prev = lruent;
  183.     l->lru_head = lruent;
  184.  
  185.     prev->l_next = next;
  186.     if (next != (LRU_ENT *) NULL)
  187.         next->l_prev = prev;
  188.  
  189.     if (l->lru_tail == lruent)
  190.         l->lru_tail = prev;
  191. }
  192.  
  193. /*
  194.  *  LRUGROW -- Grow the LRU cache
  195.  *
  196.  *    This routine is called only if we can't satisfy a user's get() request
  197.  *    using an existing buffer.  We need to rebuild the hash table so that
  198.  *    subsequent lookups work correctly, since the cache size is used to
  199.  *    compute hash keys.
  200.  *
  201.  *    Parameters:
  202.  *        l -- LRU cache to grow
  203.  *
  204.  *    Returns:
  205.  *        Zero on success, -1 on failure
  206.  */
  207.  
  208. int
  209. lrugrow(l)
  210.     LRUCACHE *l;
  211. {
  212.     int oldsz, newsz;
  213.     CACHE_ENT **new;
  214.     CACHE_ENT *ce, *nce;
  215.     int h;
  216.     int i;
  217.  
  218.     oldsz = l->lru_csize;
  219.     newsz = l->lru_csize + 1;
  220.  
  221.     /* get a new hash table */
  222.     if ((new = (CACHE_ENT **) malloc((unsigned)newsz * sizeof(CACHE_ENT *)))
  223.         == (CACHE_ENT **) NULL)
  224.         return (-1);
  225.  
  226.     /* build the new hash table */
  227.     bzero((char *) new, (size_t) (newsz * sizeof(CACHE_ENT *)));
  228.     for (i = oldsz; --i >= 0; ) {
  229.         for (ce = l->lru_cache[i]; ce != (CACHE_ENT *) NULL; ) {
  230.             nce = ce->c_chain;
  231.             h = ce->c_pgno % newsz;
  232.             ce->c_chain = new[h];
  233.             new[h] = ce;
  234.             ce = nce;
  235.         }
  236.     }
  237.  
  238.     /* get rid of the old hash table, and update the cache */
  239.     free ((char *) (l->lru_cache));
  240.     l->lru_cache = new;
  241.     l->lru_csize = newsz;
  242.  
  243.     return (0);
  244. }
  245.